#include <iostream>

using namespace std;
const int N=5*1e5+10;
int n,m;
int a[N];
struct node{
	int l,r;
	int sum;
	int lmax,rmax,tmax;
}tr[N*4];
void pushup(node& u,node& l,node& r)
{
	u.sum=l.sum+r.sum;
	u.lmax=max(l.lmax,l.sum+r.lmax);
	u.rmax=max(r.rmax,r.sum+l.rmax);
	u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}
void pushup(int u)
{
	pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
	if(l==r)
		tr[u]={l,r,a[r],a[r],a[r],a[r]};
	else{
		tr[u]={l,r};
		int mid=l+r>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u);
	}
}
void modify(int u,int x,int v)
{
	if(tr[u].l==x && tr[u].r==x)
		tr[u]={x,x,v,v,v,v};
	else{
		int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid)
		{
			modify(u<<1,x,v);
		}
		else{
			modify(u<<1|1,x,v);
		}
		pushup(u);
	}
}
node query(int u,int l,int r)
{
	if(tr[u].l>=l && tr[u].r<=r)
		return tr[u];
	else{
		int mid=tr[u].l+tr[u].r>>1;
		if(r<=mid)
		{
			return query(u<<1,l,r);
		}
		else if(l>mid)
		{
			return query(u<<1|1,l,r);
		}
		else 
		{
			auto left=query(u<<1,l,r);
			auto right=query(u<<1|1,l,r);
			node ret;
			pushup(ret,left,right);
			return ret;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	for(int i=0;i<m;i++)
	{
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op==1)
		{
			if(x>y)
				swap(x,y);
			cout<<query(1,x,y).tmax<<endl;
		}
		else{
			modify(1,x,y);
		}
	}
	return 0;
}
